时间复杂度：O(n*n)
基本思想：从数组最后一个元素开始，依次与前一个元素比较，若比前一个元素小，则与之交换位置，然后再与当前前一个元素比较，直到遇到比它大的元素为止。例如：假设数组为：$a[5]={3,4,2,5,1}$;则运算过程为：首先$1$与$5$比较，由于$1<5$，从而交换位置，数组变为$a[5]={3,4,2,1,5}$;然后$1$与当前前一个元素$2$比较，一直重复上述操作，经过一次循环后，数组变为$a[5]={1,3,4,2,5}$;第二次循环从倒数第二个元素开始……，总共循环$n-1$次就可以得到正确结果。总的来说，首先将最小的元素放在数组前面，然后放次最小的元素，依此类推。
上述过程的图解为：
注：这里的红色为要进行比较的元素。
具体实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<stdio.h>
void BubbleSort(int* arrayA,int n);
void main()
{
int arrayA[]={2,3,5,6,2,7,1,5};
int n=sizeof(arrayA)/sizeof(int);
BubbleSort(arrayA,n);
for(int i=0;i<n;i++)
printf("%d ",arrayA[i]);
}
void BubbleSort(int* arrayA,int n)
{
for(int i=0;i<n-1;i++)
{
for(int j=n-1;j>i;j--)
{
int temp=0;
if(arrayA[j]<arrayA[j-1])
{
temp=arrayA[j];
arrayA[j]=arrayA[j-1];
arrayA[j-1]=temp;
}
}
}
}
|
